import collections
class Solution:
    def numWays(self, n: int, relation, k: int) -> int:
        self.n, self.k, self.res = n, k, 0
        self.rel_dict = collections.defaultdict(list)
        for x,y in relation:
            self.rel_dict[x].append(y)
        self.search(0,0)
        return self.res

    def search(self, index, num):
        if num==self.k:
            if index==self.n-1:
                self.res += 1
            return
        for i in self.rel_dict[index]:
            self.search(i, num+1)
if __name__ == '__main__':
    n,relation,k = 5,[[0, 2], [2, 1], [3, 4], [2, 3], [1, 4], [2, 0], [0, 4]], 3
    s = Solution()
    print(s.numWays(n, relation, k))